?

Исследование различных способов организации параллельных вычислительных процессов в системах принятия решений в условиях неопределенно сти

Л.К. Птицына, Н.В. Соколова

Санкт-Петербургский государственный технический университет

Abstract — The report deals with logic models for standard parallel processes in decision-making systems. We present advanced technique for evaluating of time characteristics of multilevel decision-making sys tems with parallel data processing. Some regularities for behavior of parallel processes with different ways for serial decision rules joining are presented.

Исследование способов организации параллельных вычислительных процессов является актуальной задачей с точки зрения оценки временных затрат на их выполнение, выявления и устранения узких мест в реализ ации процессов.

Для моделирования параллельных процессов с произвольными функциями объединения последовательных фрагментов применяются многоуровневые логические модели. Как правило, в большинстве реальных систем с параллельной обработкой информации и принятия решений для комплексирования последовательных подпроцессов используются такие логические функции, как “И”, “ИЛИ” или более общий случай - пороговая функция “M из N”.

При проведении анализа логических моделей параллельных процессов с целью получения их временных характеристик каждый i-й последовательный фрагмент характеризуется распределением вероятностей времени его окончания f_i[k]. В системах принятия решений при объединении нескольких последовательных подпроцессов обычно используются следующие правила:

завершившиеся подпроцессы ожидают окончания остальных в течение некоторого промежутка времени MI [0,? );

при невыполнении условий объединения (например, если завершилось меньше подпроцессов, чем требуется) происходит возврат к началу всех последовательных фрагментов либо только тех, которые уже завершились .

Рис.1. Граф типового параллельного процесса.

Для оценки вероятности f[k] времени выполнения типового параллельного процесса, представленного на рис.1, в момент времени k, используются соотношения:

, (1)

, (2)

, (3)

. (4)

Указанные соотношения справедливы для случая объединения I последовательных фрагментов по логической функции “И” с произвольными задержками M₁

, M₂, ..., M_I и при условии принудительного возврата к началу всех подпроцессов при невозможности завершения параллельного процесса.

Представленные выражения применимы и для анализа моделей более сложных процессов, в том числе и многоуровневых. В этом случае необходимо произвести коррекцию распределений времен выполнения частных подпроцессов в соответствии с формуло й

, (5)

где f_0i[j] - вероятность окончания i-го процесса в момент j при условии, что он начался в момент времени k₀=0;

f_STRTi[k-j] - вероятность начала выполнения i-го процесса в момент (k-j).

Распределение вероятностей начала выполнения последовательного фрагмента эквивалентно распределению вероятностей срабатывания узловой вершины, запускающей данный фрагмент.

Основной временной характеристикой недетерминированного процесса является математическое ожидание времени его выполнения. Если f[k] - вероятность окончания процесса в момент времени k, то математическое ожидание времени выполнения такого процесса будет вычисляться по формуле

, (6)

где K - верхняя граница усечения распределения, после которой значение f[k], k>K, становится сто ль малым, что им можно пренебречь.

Эксперименты, проведенные с различными моделями параллельных процессов, позволили выявить ряд закономерностей.

Из четырех различных способов комплексирования последовательных фрагментов, реализующих решающие правила, - согласно логической функции “И” с нулевой и бесконечной задержками, согласно функции “ИЛИ”, последовательное выполнение подпроц ессов, - наилучшими временными характеристиками обладает процесс, в котором формирование окончательного решения происходит по функции “ИЛИ”, а наихудшими - процесс с последовательным выполнением всех решающих правил. Однако при уменьшении вероятности обнаружения события в каком-либо из промежуточных состояний (ситуация ложной тревоги) дольше всего будет выполняться процесс, реализующий комплексирование по “И” с нулевой задержкой.

По мере увеличения степени параллельности математическое ожидание времени выполнения параллельного процесса при объединении по "И" возрастает нелинейно.

Математическое ожидание времени выполнения параллельного процесса при комплексировании фрагментов по пороговой функции “M из N” увеличивается нелинейно с увеличени ем порога М.

Факт проявления ожидаемого события оказывает существенное влияние на соотношение математических ожиданий времен выполнения параллельных процессов.

Введение задержки комплексирования снижает временные затраты на реализацию параллельного процесса даже в случае единичной задержки.

Проведенные исследования показали, что оптимальный выбор числа частных решающих правил и способов их объединения требует количественной оценки статистических характеристик времен выполнения параллельных про цессов и их сопоставления при различных способах комплексирования.

Site of Information Technologies
Designed by inftech@webservis.ru.